Pada 12 Oktober 1937, sebuah syarikat perkapalan enjin stim singapura yang berpusat di Liverpool dan Imperial Airways telah menghantar permohonan kepada kerajaan penjajah di Pulau Pinang dan Singapura untuk memulakan penerbangan berjadual yang menghubungkan kedua-dua bandar ini. Malayan Airways Limited (MAL) telah ditubuhkan namun perkhidmatan berbayar untuk penumpang yang pertama sekali hanya dapat diperkenalkan 10 tahun kemudiannya pada 2 Februari 1947 dan penerbangan sulung yang hanya membawa 5 orang penumpang ini adalah untuk ke KUala Lumpur, bukan Pulau Pinang. Dalam tahun yang sama, MAL meluaskan operasi penerbangannya ke Jakarta, Medan, Palembang dan Saigon daripada hub utamanya di Singapura.

Pada tahun 1957, syarikat penerbangan ini dijadikan syarikat milik kerajaan. Dengan ketibaan pesawat Bristol Britannia yang mampu membawa 84 penumpang pada tahun 1960, syarikat penerbangan ini memulakan operasi jarak jauh pertamanya ke Hong Kong.

Apabila negara Malaysia ditubuhkan, nama syarikat ini ditukar kepada Malaysian Airways Limited pada November 1963. Kemudian, apabila Singapura berpisah daripada Kesatuan Malaysia pada 9 Ogos 1965, kerajaan Malaysia dan Singapura mengambil alih saham majoriti daripada BOAC dan pemegang saham yang lain dan syarikat ini bertukar nama menjadi Penerbangan Malaysia-Singapura.

Selepas 20 tahun memulakan operasinya, syarikat ini telah menggunakan pelbagai jenis pesawat seperti Comet IV, enam Fokker F27, lapan Douglas DC-3 dan dua Twin Pioneers dan mempunyai tenaga kerja seramai 2,400 orang. Pada 3 April 1971, syarikat penerbangan ini dibahagikan kepada dua syarikat, iaitu Singapore Airlines dan Malaysia Airlines Systems (MAS). Menjelang tahun 1972, MAS telah meluaskan operasi kepada lebih 34 destinasi domestik dan enam destinasi antarabangsa.

Pada 15 Oktober 1987, nama perdangangan syarikat ini ditukar kepada Malaysia Airlines.